<!DOCTYPE html>
<html>
<head>
<title>周志华《机器学习》课后习题解答系列（五）：Ch4.3 - 编程实现ID3算法</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<style type="text/css">
/* GitHub stylesheet for MarkdownPad (http://markdownpad.com) */
/* Author: Nicolas Hery - http://nicolashery.com */
/* Version: b13fe65ca28d2e568c6ed5d7f06581183df8f2ff */
/* Source: https://github.com/nicolahery/markdownpad-github */

/* RESET
=============================================================================*/

html, body, div, span, applet, object, iframe, h1, h2, h3, h4, h5, h6, p, blockquote, pre, a, abbr, acronym, address, big, cite, code, del, dfn, em, img, ins, kbd, q, s, samp, small, strike, strong, sub, sup, tt, var, b, u, i, center, dl, dt, dd, ol, ul, li, fieldset, form, label, legend, table, caption, tbody, tfoot, thead, tr, th, td, article, aside, canvas, details, embed, figure, figcaption, footer, header, hgroup, menu, nav, output, ruby, section, summary, time, mark, audio, video {
  margin: 0;
  padding: 0;
  border: 0;
}

/* BODY
=============================================================================*/

body {
  font-family: Helvetica, arial, freesans, clean, sans-serif;
  font-size: 14px;
  line-height: 1.6;
  color: #333;
  background-color: #fff;
  padding: 20px;
  max-width: 960px;
  margin: 0 auto;
}

body>*:first-child {
  margin-top: 0 !important;
}

body>*:last-child {
  margin-bottom: 0 !important;
}

/* BLOCKS
=============================================================================*/

p, blockquote, ul, ol, dl, table, pre {
  margin: 15px 0;
}

/* HEADERS
=============================================================================*/

h1, h2, h3, h4, h5, h6 {
  margin: 20px 0 10px;
  padding: 0;
  font-weight: bold;
  -webkit-font-smoothing: antialiased;
}

h1 tt, h1 code, h2 tt, h2 code, h3 tt, h3 code, h4 tt, h4 code, h5 tt, h5 code, h6 tt, h6 code {
  font-size: inherit;
}

h1 {
  font-size: 28px;
  color: #000;
}

h2 {
  font-size: 24px;
  border-bottom: 1px solid #ccc;
  color: #000;
}

h3 {
  font-size: 18px;
}

h4 {
  font-size: 16px;
}

h5 {
  font-size: 14px;
}

h6 {
  color: #777;
  font-size: 14px;
}

body>h2:first-child, body>h1:first-child, body>h1:first-child+h2, body>h3:first-child, body>h4:first-child, body>h5:first-child, body>h6:first-child {
  margin-top: 0;
  padding-top: 0;
}

a:first-child h1, a:first-child h2, a:first-child h3, a:first-child h4, a:first-child h5, a:first-child h6 {
  margin-top: 0;
  padding-top: 0;
}

h1+p, h2+p, h3+p, h4+p, h5+p, h6+p {
  margin-top: 10px;
}

/* LINKS
=============================================================================*/

a {
  color: #4183C4;
  text-decoration: none;
}

a:hover {
  text-decoration: underline;
}

/* LISTS
=============================================================================*/

ul, ol {
  padding-left: 30px;
}

ul li > :first-child, 
ol li > :first-child, 
ul li ul:first-of-type, 
ol li ol:first-of-type, 
ul li ol:first-of-type, 
ol li ul:first-of-type {
  margin-top: 0px;
}

ul ul, ul ol, ol ol, ol ul {
  margin-bottom: 0;
}

dl {
  padding: 0;
}

dl dt {
  font-size: 14px;
  font-weight: bold;
  font-style: italic;
  padding: 0;
  margin: 15px 0 5px;
}

dl dt:first-child {
  padding: 0;
}

dl dt>:first-child {
  margin-top: 0px;
}

dl dt>:last-child {
  margin-bottom: 0px;
}

dl dd {
  margin: 0 0 15px;
  padding: 0 15px;
}

dl dd>:first-child {
  margin-top: 0px;
}

dl dd>:last-child {
  margin-bottom: 0px;
}

/* CODE
=============================================================================*/

pre, code, tt {
  font-size: 12px;
  font-family: Consolas, "Liberation Mono", Courier, monospace;
}

code, tt {
  margin: 0 0px;
  padding: 0px 0px;
  white-space: nowrap;
  border: 1px solid #eaeaea;
  background-color: #f8f8f8;
  border-radius: 3px;
}

pre>code {
  margin: 0;
  padding: 0;
  white-space: pre;
  border: none;
  background: transparent;
}

pre {
  background-color: #f8f8f8;
  border: 1px solid #ccc;
  font-size: 13px;
  line-height: 19px;
  overflow: auto;
  padding: 6px 10px;
  border-radius: 3px;
}

pre code, pre tt {
  background-color: transparent;
  border: none;
}

kbd {
    -moz-border-bottom-colors: none;
    -moz-border-left-colors: none;
    -moz-border-right-colors: none;
    -moz-border-top-colors: none;
    background-color: #DDDDDD;
    background-image: linear-gradient(#F1F1F1, #DDDDDD);
    background-repeat: repeat-x;
    border-color: #DDDDDD #CCCCCC #CCCCCC #DDDDDD;
    border-image: none;
    border-radius: 2px 2px 2px 2px;
    border-style: solid;
    border-width: 1px;
    font-family: "Helvetica Neue",Helvetica,Arial,sans-serif;
    line-height: 10px;
    padding: 1px 4px;
}

/* QUOTES
=============================================================================*/

blockquote {
  border-left: 4px solid #DDD;
  padding: 0 15px;
  color: #777;
}

blockquote>:first-child {
  margin-top: 0px;
}

blockquote>:last-child {
  margin-bottom: 0px;
}

/* HORIZONTAL RULES
=============================================================================*/

hr {
  clear: both;
  margin: 15px 0;
  height: 0px;
  overflow: hidden;
  border: none;
  background: transparent;
  border-bottom: 4px solid #ddd;
  padding: 0;
}

/* TABLES
=============================================================================*/

table th {
  font-weight: bold;
}

table th, table td {
  border: 1px solid #ccc;
  padding: 6px 13px;
}

table tr {
  border-top: 1px solid #ccc;
  background-color: #fff;
}

table tr:nth-child(2n) {
  background-color: #f8f8f8;
}

/* IMAGES
=============================================================================*/

img {
  max-width: 100%
}
</style>
</head>
<body>
<p>这里采用<strong>Python-sklearn</strong>的方式，环境搭建可参考<a href="http://blog.csdn.net/snoopy_yuan/article/details/61211639"> 数据挖掘入门：Python开发环境搭建（eclipse-pydev模式）</a>.</p>
<p>相关答案和源代码托管在我的Github上：<a href="https://github.com/PY131/Machine-Learning_ZhouZhihua">PY131/Machine-Learning_ZhouZhihua</a>.</p>
<h2>4.3 编程实现ID3算法</h2>
<blockquote>
<p><img src="Ch4/4.3.png" />
<img src="Ch4/4.3.1.png" /></p>
</blockquote>
<p>这里采用了自己编程实现和调用sklearn库函数两种不同的方式，详细解答和编码过程如下：（<a href="https://github.com/PY131/Machine-Learning_ZhouZhihua/tree/master/ch4_decision_tree/4.3_ID3">查看完整代码</a>）：</p>
<h3>1.获取数据、查看数据、预分析</h3>
<p>这里由数据表生成.csv文件（注意<strong>中文字符的编码格式</strong>）。采用<strong>pandas<strong>.read_csv()读取数据，然后采用</strong>seaborn</strong>可视化部分数据来进行初步判断。</p>
<p>观察数据可知，变量包含'色泽'等8个属性，其中6个<strong>标称属性</strong>，2个<strong>连续属性</strong>。类标签为西瓜是否好瓜（两类）：</p>
<p>下面是一些数据可视化图像：</p>
<p>下图是含糖率和密度两个连续变量的可视化图，这个图在之前的练习中也有出现：</p>
<p><img src="Ch4/4.3.2.png" /></p>
<p>下图则是更多的变量两两组合可视化图：</p>
<p><img src="Ch4/4.3.3.png" /></p>
<p>基于可视化手段进行一些分析，看以大概了解数据的分布及其与类别的关系。</p>
<h3>2.自己编程实现ID3算法</h3>
<p>在进行编程之前，先做一些分析如下：</p>
<ul>
<li>对于树形结构，可以创建<strong>节点类</strong>来进行操作，根据书p74决策树基本算法，广泛采用<strong>递归操作</strong>；</li>
<li>对于连续属性（密度、含糖率），参考书p83，对其进行<strong>离散化</strong>（可采用二分法）；</li>
<li>对于标称属性（色泽、纹理等），考虑<strong>Python字典</strong>，方便操作其特征类别（如：'色泽' -&gt; '青绿'，'乌黑'，'浅白'）；</li>
<li>由于数据集完整，这里暂不考虑缺值问题（若需考虑，可参考书p86-87的加权思路 -&gt; C4.5算法）；</li>
</ul>
<p>下面是实现过程：</p>
<h5>2.1 建立决策树节点类</h5>
<p>该节点类包含当前节点的属性，向下划分的属性取值，节点的类标签（叶节点有效，为通用性而保留所有节点类标签）；</p>
<p>样例代码如下：</p>
<pre><code>'''
definition of decision node class

@variable attr: attribution as parent for a new branching 
@variable attr_down: dict: {key, value}
            key:   categoric:  categoric attr_value 
                   continuous: '&lt;=div_value' for small part
                               '&gt;div_value' for big part
            value: children (Node class)
@variable label： class label (the majority of current sample labels)
''' 
class Node(object): 
    def __init__(self, attr_init=None, attr_down_init={}, label_init=None):  
        self.attr = attr_init  
        self.attr_down = attr_down_init
        self.label = label_init  
</code></pre>

<h5>2.2 递归实现决策树生成算法主体</h5>
<p>基本的决策树生成算法参照书p74-图4.2，如下所示：</p>
<blockquote>
<p><img src="Ch4/4.3.4.png" /></p>
</blockquote>
<p>下面是算法主体代码，注意对连续变量和离散变量的不同操作：</p>
<pre><code>''' 
Branching for decision tree using recursion 

@param df: the pandas dataframe of the data_set
@return root: Node, the root node of decision tree
'''  
def TreeGenerate(df):
    # generating a new root node
    new_node = Node(None, None, {})
    label_arr = df[df.columns[-1]]

    label_count = NodeLabel(label_arr)
    if label_count:  # assert the label_count isn's empty
        new_node.label= max(label_count, key=label_count.get) 

        # end if there is only 1 class in current node data
        # end if attribution array is empty
        if len(label_count) == 1 or len(label_arr) == 0:
            return new_node

        # get the optimal attribution for a new branching
        new_node.attr, div_value = OptAttr(df)

        # recursion
        if div_value == 0:  # categoric variable
            value_count = ValueCount(df[new_node.attr]) 
            for value in value_count:
                df_v = df[ df[new_node.attr].isin([value]) ]  # get sub set
                # delete current attribution
                df_v = df_v.drop(new_node.attr, 1)  
                new_node.attr_down[value] = TreeGenerate(df_v)

        else:  # continuous variable # left and right child
            value_l = &quot;&lt;=%.3f&quot; % div_value
            value_r = &quot;&gt;%.3f&quot; % div_value
            df_v_l = df[ df[new_node.attr] &lt;= div_value ]  # get sub set
            df_v_r = df[ df[new_node.attr] &gt; div_value ]

            new_node.attr_down[value_l] = TreeGenerate(df_v_l)
            new_node.attr_down[value_r] = TreeGenerate(df_v_r)

    return new_node
</code></pre>

<h5>2.3 最优划分属性选择-信息增益判断</h5>
<p><strong>ID3算法</strong>采用<strong>信息增益最大化<strong>来实现最优划分属性的选择，这里主要的挑战是离散和连续两种属性变量的分别操作。对于离散变量（categoric variable），参考书p75-77内容实现，对于连续变量（continuous variable），采用书p83-85所介绍的</strong>二分法</strong>实现。</p>
<p>相关内容如<strong>信息熵、信息增益最大化、二分法</strong>等可参考书p75-76及p84页内容。</p>
<p>具体的实现代码：<a href="https://github.com/PY131/Machine-Learning_ZhouZhihua/blob/master/ch4_decision_tree/4.3_ID3/src/decision_tree.py">查看完整代码</a>。</p>
<p>如下所示为综合了离散类别变量和连续变量的信息增益计算代码实现：</p>
<pre><code>'''
calculating the information gain of an attribution

@param df:      dataframe, the pandas dataframe of the data_set
@param attr_id: the target attribution in df
@return info_gain: the information gain of current attribution
@return div_value: for discrete variable, value = 0
               for continuous variable, value = t (the division value)
'''  
def InfoGain(df, index):
    info_gain = InfoEnt(df.values[:,-1])  # info_gain for the whole label
    div_value = 0  # div_value for continuous attribute

    n = len(df[index])  # the number of sample

    # 1.for continuous variable using method of bisection
    if df[index].dtype == (float, int):
        sub_info_ent = {}  # store the div_value (div) and it's subset entropy

        df = df.sort([index], ascending=1)  # sorting via column
        df = df.reset_index(drop=True)

        data_arr = df[index]
        label_arr = df[df.columns[-1]]

        for i in range(n-1):
            div = (data_arr[i] + data_arr[i+1]) / 2
            sub_info_ent[div] = ( (i+1) * InfoEnt(label_arr[0:i+1]) / n ) \
                              + ( (n-i-1) * InfoEnt(label_arr[i+1:-1]) / n )
        # our goal is to get the min subset entropy sum and it's divide value
        div_value, sub_info_ent_max = min(sub_info_ent.items(), key=lambda x: x[1])
        info_gain -= sub_info_ent_max

    # 2.for discrete variable (categoric variable)
    else:
        data_arr = df[index]
        label_arr = df[df.columns[-1]]
        value_count = ValueCount(data_arr)

        for key in value_count:
            key_label_arr = label_arr[data_arr == key]
            info_gain -= value_count[key] * InfoEnt(key_label_arr) / n

    return info_gain, div_value
</code></pre>

<h5>2.4 划分训练集和测试集进行测试</h5>
<p>首先给出<strong>预测函数</strong>，采用简单的向下搜索即可实现。<a href="https://github.com/PY131/Machine-Learning_ZhouZhihua/blob/master/ch4_decision_tree/4.3_ID3/src/decision_tree.py">查看完整代码</a>。</p>
<p>通过多次划分训练集和测试集，评估出所生成的完全决策树的预测精度，下面是几种不同情况下的结果和分析：</p>
<ul>
<li>
<p>训练集为整个数据样本的情况：</p>
<pre><code>accuracy: 1.000  1.000  1.000  1.000  1.000  1.000  1.000  1.000  1.000  1.000  
average accuracy: 1.000
</code></pre>

<p>此时预测准度为100%，结果证明了<strong>题4-1</strong>。</p>
<p>采用<strong>pydotplus.graphviz</strong>绘图库，可以画出这样一棵完全决策树如下图（<a href="https://github.com/PY131/Machine-Learning_ZhouZhihua/blob/master/ch4_decision_tree/4.3_ID3/src/decision_tree.py">点击查看绘图程序</a>）：</p>
<p><img src="Ch4/4.3_decision_tree_ID3.png" /></p>
</li>
<li>
<p>训练集与测试集各取一半：</p>
<pre><code>accuracy: 0.556  0.778  0.333  0.778  0.444  0.333  0.667  0.444  0.778  0.333  
average accuracy: 0.544
</code></pre>

<p>多次实验预测准度均在55%左右（几乎等同于随机预测），说明此时模型无实用性。</p>
</li>
<li>
<p>按照K折交叉验证模型（k=5）：</p>
<pre><code>accuracy: 1.000  0.000  0.667  1.000  0.000  
average accuracy: 0.533
</code></pre>

<p>结果精度依然很不理想，可以看到，不同的训练集与测试集的划分导致结果差别很大，这主要是由于数据量太少的缘故。</p>
</li>
<li>
<p>只分析离散属性：</p>
<pre><code>accuracy: 1.000  0.000  0.333  0.667  0.000  
average accuracy: 0.400
</code></pre>

<p>此时由于特征信息减少，模型更差了。</p>
</li>
</ul>
<p>综上，为提高决策树泛化预测精度，需要进一步对其进行<strong>剪枝</strong>。</p>
<p>关于剪枝实现可参考下一题。</p>
<hr />
<p>相关参考：</p>
<p>1.seaborn/matplotlib可视化、中文字符处理：</p>
<ul>
<li><a href="http://seaborn.pydata.org/tutorial/categorical.html">seaborn官网 - Plotting with categorical data</a></li>
<li><a href="https://github.com/mwaskom/seaborn/issues/1009">seaborn显示中文 - The solution of display chinese in seaborn plot</a></li>
<li><a href="https://segmentfault.com/a/1190000000621721">Linux下解决matplotlib中文乱码的方法</a></li>
<li><a href="http://www.cnblogs.com/TsengYuen/archive/2012/05/22/2513290.html">Unicode和Python的中文处理</a></li>
</ul>
<p>2.python基础知识： </p>
<ul>
<li><a href="http://blog.csdn.net/moodytong/article/details/7647684">Python学习 - python字典</a></li>
<li><a href="https://zhidao.baidu.com/question/328905513600600605.html">Python从字符串中提取数字 - 正则表达式</a></li>
</ul>
<p>3.决策树绘制相关：</p>
<ul>
<li><a href="http://scikit-learn.org/stable/modules/tree.html">sklearn官网 - Decision Trees</a></li>
<li><a href="http://pydotplus.readthedocs.io/reference.html#module-pydotplus.graphviz">pydotplus官网 - graphviz的API</a></li>
<li><a href="https://wenku.baidu.com/view/207d623b76a20029bc642de0.html">GraphViz常用属性学习笔记</a></li>
<li><a href="http://www.aiuxian.com/article/p-835489.html">pydot包的安装和使用</a></li>
</ul>
<hr />

</body>
</html>
<!-- This document was created with MarkdownPad, the Markdown editor for Windows (http://markdownpad.com) -->
